Networks are used to transmit data (also called network traffic) between network devices connected by links. A path used for transmission of data between two network devices may go through several intermediate network devices and links. A network device may be a router, a computer, a processor in a multiprocessor computer, or any other device as long as it is capable of performing the required network tasks.
A network in general has multiple paths between a given source and a given destination, uses some routing protocol to select a set of the available paths and should be capable of tolerating some links between network devices breaking. One example of such a network is a packet-switched network transmitting packets consisting of binary data. The packets are sent from one network device (also called a host or a node) to another network device, usually through several intermediate network devices known as routers that determine the next hop, i.e. the next network device in the path to the destination.
The transmission of data between network devices, such as routers, may be accomplished using a variety of technologies: wires, phone lines, optical links, wireless links, and others. The low-level protocols used by implementations of these technologies are known as physical layer (or level 1) protocols.
Internet Protocol (IP) based networks, i.e., networks conforming to Request for Comments (RFC) 0791 and RFC 1349 distributed by the Internet Engineering Task Force (IETF) are a popular type of packet-switched networks. The IETF develops, distributes, and maintains a variety of network standards commonly referred to by their numbers as RFCs. A global IP network comprising a large number of interconnected local networks is known as the Internet. A full set of RFCs is available at the IETF's Internet site.
IP is an example of a network layer (or level 3) protocol. Network layer protocols rely on link layer (or level 2) protocols. These protocols may also involve routing packets. A popular type of link layer protocol is Ethernet.
A host is connected to at least one other host. A network router is a host connected to two or more other hosts. Hereinafter, these other hosts will be called the hosts' neighbors and the connection ports on the hosts will be called interfaces. A transmission over a single link between two neighbors is called a “hop”. Upon receiving a packet, a router decides the best, for some definition of best, next hop to use, such that the packet eventually arrives at its destination. This decision is usually made using the information carried within the packet, such as the packet's destination host. A router may also use information about the network's topology, i.e. how other hosts are interconnected to determine which interface to direct an incoming packet. Another variable that the router may consider in making its decision is the input interface on which the packet has arrived. Alternatively, a packet may simply carry a label, which the router would use to determine the output interface by using a table per input interface indexed by the labels and containing the output interfaces. One such label-based forwarding mechanism is known as Multi-Protocol Label Switching (MPLS, RFC 3031).
Normally, routing selects the lowest cost path to the destination. Given a network topology, each link in each direction is assigned a positive number, its cost. Given this information, the path chosen for forwarding a packet is the route with the least sum of costs. Each router stores in its memory the network topology and the relevant link costs and for each destination D determines to which neighbor it sends a D-addressed packet so that it travels the lowest cost path. However, other considerations may apply, such as reducing strain on some links in the network, or prioritizing delivery of some packets over others.
After a change in network topology (for example, when a link between two hosts is broken), the routing decisions made by routers may also change. In other words, a packet arriving to a router from interface A may be forwarded to interface B before the change and to interface C after the change. To minimize network traffic loss after a topology change, it is preferable that even before network routers become aware of what the new topology is and make proper adjustments in their traffic forwarding strategy, they continue to forward packets to their destinations. In other words, it is preferable that the forwarding strategy does not cause a loss of traffic in case of topology change even when forwarding decisions are based on stale (pre-change) topology and before even the occurrence of the change becomes known.
Obviously, this task is simply impossible in some cases (to take an extreme example, when all links in a network fail) and trivial in others (for example, when an extra link or links between routers are added to a network without other changes, the old forwarding strategy would remain functional by simply ignoring the added links). However, usually links between routers fail one at a time and networks have enough link redundancy to allow traffic redirection. Many routing algorithms, such as OSPF, rely on link state advertisements (LSAs) to inform all the other routers in a routing group of link status. In the case of a down link, the routers directly connected to that link (that are still able to function) broadcast (flood) a new LSA indicating the down link. These routers compute routes based on the new information and install those new routes. As the other routers in the routing group receive the LSA, they also recompute routes based on the new information and install those new routes as well.
The goal is for all of the routers to compute the same routes. Once their view of the network from the LSAs becomes consistent, the routes become identical since they use algorithms that provide identical results to compute the routes. However, since the information takes a different amount of time to get to each router, each router may take a different amount of time to compute the new routes, and there may be more than one link event at any given time, different routers may have different routes installed for some time after a topology change. Inconsistent routes may cause routing loops (closed-loops), where traffic is forwarded in a ring of routers, never to reach their final destination.